\section{Introducci\'on}
Nos proponen el siguiente juego:
\\
\\
Dado una secuencia de \textbf{n} cartas, cada jugador en su turno deber\'a robar x cantidad de cartas consecutivas empezando del lado derecho o del lado izquierdo (x > 0).
\\
Luego esas cartas ser\'an retiradas de la secuencia y le tocar\'a el turno al otro jugador que har\'a lo mismo hasta que se hayan tomado todas las cartas.
\\
Al finalizar el juego se sumar\'an los valores de las cartas robadas por cada jugador y el que tenga la suma mayor ser\'a el ganador.
\\
\\
Se nos pidi\'o implementar un algoritmo que juege de manera \'optima el juego propuesto. Esto es, dada la secuencia inicial de cartas, deberemos decidir cuantas cartas levantar\'a cada jugador en cada turno y de que lado del mazo tal que maximize la diferencia por la que gana el jugador o minimize su derrota.
\\
\\
La entrada del algoritmo ser\'a la siguiente:
\begin{itemize}
\item Un entero \textbf{n} $\rightarrow$ Representar\'a el n\'umero inicial de cartas.
\item $n$ enteros \textbf{$C_1,C_2,...C_n$} $\rightarrow$ Representar\'an los valores de las distintas cartas.
\end{itemize}
\\
La salida que el algoritmo deber\'a devolver es:
\begin{itemize}
\item La cantidad de turnos en la que termina el juego.
\item El total de puntos de cada jugador.
\item Cu\'antas cartas y de que lado se roban en que cada turno
\end{itemize}
\\
\subsection{Ejemplo}
Una intancia v\'alida de entrada podr\'ia ser:
\\
$$n = 5, C_1=5, C_2=-6, C_3=-10, C_4=9, C_5=2$$
\\ 
En este caso una posible soluci\'on \'optima ser\'ia:
\begin{itemize}
\item Turnos $\rightarrow$ 3
\item Puntaje jugador1 $\rightarrow$ 1
\item Puntaje jugador2 $\rightarrow$ -1
\item Primer turno $\rightarrow$ Se roban 2 cartas de la derecha.
\item Segundo turno $\rightarrow$ Se roban 2 cartas de la Izquierda.
\item Tercer turno $\rightarrow$ Se roba 1 carta de la izquierda.
\end{itemize}



\section{Idea General de Resoluci\'on}

Para la soluci\'on del problema vamos a utilizar programaci\'on din\'amica, esto es, para construir la soluci\'on \'optima, primero iremos resolviendo subproblemas de tamaño menor, guardandolos para que no sea necesario resolverlos una segunda vez, hasta llegar a la soluci\'on deseada.
\\
\\
Lo que haremos b\'asicamente es valernos de una funci\'on recursiva que calcular\'a para cada posible robo de cartas diferente que tengamos en ese turno, el puntaje del mismo. Y lo comparar\'a con el m\'aximo puntaje obtenido por el adversario en la siguiente jugada.
\\
Para calcular este m\'aximo puntaje puntaje del adversario har\'a exactamente lo mismo pero esta vez solo teniendo en cuenta las cartas del mazo que no fueron robadas.
\\
\\
Cada vez que se logre calcular uno de estos m\'aximos, ya sea porque se llego a un caso base (cuando se acaban las cartas) o a un valor ya calculado, se guardar\'a en una matriz la diferencia de puntajes de los dos jugadores. Y en otra matriz (en la misma posici\'on) la cantidad de cartas de cartas que se robaron (le pondremos valores negativos si se roban de la derecha).
\begin{itemize}
\item La diferencia de puntajes para la secuencia completa de N cartas se guardar\'a en la posici\'on [0][n-1] 
\item La diferencia de puntajes para la secuencia sin la \'ultima carta se guardar\'a en la posici\'on [0][(n-1)-2]
\item La diferencia de puntajes para la secuencia sin la primer carta se guardar\'a en la posici\'on [1][n-1]
\item Siguiendo as\'i para el resto, podemos deducir la siguiente formula general:
\begin{itemize}
\item En la posici\'on [i][(n-1)-j] se guardar\'a la diferencia de puntajes para la secuencia sin las primeras i cartas ni las \'ultimas j cartas
\end{itemize}
\end{itemize}
\\
\\
\\
Siguiendo el ejemplo anterior:
\\
\\
\begin{tabular}{| l | l |}
\hline
~~~Mazo \\ \hline
5 -6 -10 9 2  \\ \hline
\end{tabular}
\quad \quad \quad
\begin{tabular}{| l | l |}
\hline
~~~~~~~MatrizDiferencia\\ \hline
$
\begin{vmatrix}
-- & 11 & 9  & 0  & 2  \\
-- & -- & 4  & 5  & 7  \\
-- & -- & -- & 19 & 21 \\
-- & -- & -- & -- & 11 \\
-- & -- & -- & -- & -- \\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\quad \quad \quad
\begin{tabular}{| l | l |}
\hline
~~~~~~~~MatrizJugadas\\ \hline
$
\begin{vmatrix}
-- & 1  & 2  & -1 & -1 \\
-- & -- & 1  & -1 & -2 \\
-- & -- & -- & -1 & -2 \\
-- & -- & -- & -- & -2 \\
-- & -- & -- & -- & -- \\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\\
\\
\\
Para poder extraer de estas matrices la salida que nos interesa utilizaremos la MatrizJugadas y operaremos de la siguiente manera:
\begin{itemize}
\item Empezaremos por la posici\'on [0][n-1] que es la que coincide para cuando tenemos la secuencia entera.
\begin{itemize}
\item MatrizJugadas[0][4] = \textbf{-1} $\rightarrow$ El primer jugador toma una carta de la derecha
\item Puntaje Jugador1 = 2
\item Puntaje Jugador2 = 0
\end{itemize}
\item Pasamos a la posicion [0][3] (sin la \'ultima carta)
\begin{itemize}
\item MatrizJugadas[0][3] = \textbf{-1} $\rightarrow$ El segundo jugador toma una carta de la derecha
\item Puntaje Jugador1 = 2
\item Puntaje Jugador2 = 9
\end{itemize}
\item Pasamos a la posicion [0][2] (sin las \'ultimas 2 carta)
\begin{itemize}
\item MatrizJugadas[0][2] = \textbf{2} $\rightarrow$ El primer jugador toma dos cartas de la izquierda
\item Puntaje Jugador1 = 2 + 5 +(-6) = 1
\item Puntaje Jugador2 = 9
\end{itemize}
\item El jugador 2 toma la \'ultima carta de la secuencia
\begin{itemize}
\item Puntaje Jugador1 = 2 + 5 +(-6) = 1
\item Puntaje Jugador2 = 9 +(-10) = -1
\end{itemize}
\end{itemize}


Podemos apreciar que la diferencia de puntaje de los jugador es 2, que es lo que teniamos guardado en MatrizDiferencia[0][4]

\section{Pseudoc\'odigo}




\begin{algorithm}
\begin{algorithmic}[1]\parskip=1mm
\caption{int robaNumeros(mazo[], i, j, MatrizDiferencia[][], MatrizJugadas[][])}

  \STATE{\textbf{Si} Estoy en la parte de abajo de la matriz (i>j)}
    \STATE{\quad \textbf{Devuelvo} 0}
  
  \STATE{\textbf{Si} queda una sola carta (i==j)}
    \STATE{\quad \textbf{Devuelvo} el valor de la carta}
    
  \STATE{\textbf{Sino}}
    \STATE{\quad \textbf{Si} no ten\'ia calculada la posici\'on [i][j]}
      \STATE{\quad \quad Maximo = -9999 (valor a guardar en MatrizDiferencia)}
      \STATE{\quad \quad pass   = 0  (valor a guardar en MatrizJugadas)}
      \STATE{\quad \quad \textbf{Para} K desde 1 hasta la cantidad de cartas de la secuencia en esta iteraci\'on (j-i+1) \textbf{Do}}
        \STATE{\quad \quad \quad suma\_izq = Suma de robar K cartas del lado izquierdo}
        \STATE{\quad \quad \quad suma\_der = Suma de robar K cartas del lado derecho}
        \STATE{\quad \quad \quad robaDerecha = suma\_der - robanumeros(mazo, i, j-k-1, matrizDiferencia, matrizJugadas)}
        \STATE{\quad \quad \quad robaIzquierda = suma\_izq - robanumeros(mazo, i+k+1, j, matrizDiferencia, matrizJugadas)}   
        \STATE{\quad \quad \quad \textbf{Si} robaIzquierda > robaDerecha}
          \STATE{\quad \quad \quad \quad  \textbf{Si} robaIzquierda > maximo}
            \STATE{\quad \quad \quad \quad \quad pass = k+1; maximo = robaIzquierda}
        \STATE{\quad \quad \quad \textbf{Sino}}
          \STATE{\quad \quad \quad \quad  \textbf{Si} robaDerecha > maximo}
            \STATE{\quad \quad \quad \quad \quad pass = -(k+1); maximo = robaDerecha}
      \STATE{\quad \quad matrizJugadas[i][j] = pass}
      \STATE{\quad \quad matrizDiferencia[i][j] = maximo}
    \STATE{\quad \textbf{Devuelvo} matrizDiferencia[i][j]}
            
 \end{algorithmic}
\end{algorithm}


\section{Analisis de la Complejidad}

\textbf{Nota:} Llamaremos subsecuencia a la secuencia de cartas que queda despu\'es de sacarle al mazo original \textbf{x} cantidad de cartas de la derecha y otra \textbf{z} cantidad de la izquierda.
\begin{itemize}
\item Crear e inicializar las matrices tiene una complejidad de $O(n^2)$
\item Para un mazo de \textbf{n} cartas podemos acotar la cantidad de subsecuencias diferentes por $(n^2)$ de la siguiente manera:
\[
\# subsecuenciasDiferenes = \sum_{i=0}^{i<n} \sum_{j=0}^{i+j < n} 1  =  \frac{n^2 + n}{2} \leq n^2
\]
(siendo \textbf{i} la cantidad de cartas que se sacan del lado izquierdo y \textbf{j} la cantidad que se saca del lado derecho)
\item Cada vez que se llame a la recusi\'on para una posici\'on ya calculada la complejidad ser\'a $O(1)$ y no habr\'a m\'as llamadas recursivas.
\item En el caso en el que no este calculada previamente deberemos analizar:
\begin{itemize}
\item El costo de calcular suma\_der tendr\'a una complejidad de $O(k)$ con $k<n$. Lo mismo para suma\_izq.
\item Para cada valor de k diferente tendremos 2 llamadas recursivas, $(2.k)$ en total.
\end{itemize}

\item Como dijimos que como m\'aximo hay $n^2$ subsecuencias diferentes solo llamaremos a lo sumo $n^2$ veces a la llamada recursiva con valores que no hallamos calculado previamente, con complejidad $O(k)$ para cada una.\\
Y como m\'aximo $(n^2 * 2k)$ llamadas para posiciones ya calculadas, con complejidad $O(1)$ para cada una. 

\item Luego la complejidad del peor caso del algoritmo ser\'a 
\[
O((n^2) + (n^2)*k + (n^2*k)*1 = O(n^2 + n^3 + n^3) = O(n^3)~~~~~~~~~~~~~~~~k\leq n
\]
\end{itemize}
Si no hubiesemos guardado los valores ya calculados en nuestra MatrizDiferencia, es decir, si no hubiesemos utilizado una t\'ecnica de programaci\'on din\'amica, la cantidad de subsecuencias que hubiesemos tenido que analizar hubiesen sido muchas m\'as, y la complejidad del algoritmo se volver\'ia exponencial.


\section{Correctitud}

Una soluci\'on \'optima es aquella en la que ambos jugadores suman la mayor cantidad de puntos posibles al final del juego.
\\
\\
Para poder usar programaci\'on din\'amica en nuestro algoritmo primero necesitamos justificar el principio de optimalidad, lo cual es relativamente sencillo.
\\
Las subsoluciones \'optimas son todas aquellas subsecuencias de cartas que quedan luego de terminado el turno de un jugador.
\\
\begin{itemize}
\item Si al comenzar tengo n cartas en el maso
\item Supongo S1 soluci\'on \'optima
\begin{itemize}
\item S1 = t1 t2...tm      (siendo ti los turnos) 
\end{itemize}
\item Supongo sin perdida de generalidad que en t1 el jugador 1 roba k cartas del lado derecho\\
Luego me quedan en el maso las cartas k+1...n
\item Supongo S2 soluci\'on \'optima para esta secuencia
\begin{itemize}
S2 = r1...rl
\end{itemize}
\item r1 es turno del jugador 2. Si los puntos que suma el jugador 2 en total en todos los turnos de S2 es  mayor que lo que sumaba el en S1, nos lleva a un absurdo, ya que 
habiamos supuesto a S1 soluci\'on \'optima, lo cual significa que el jugador 2 suma la mayor cantidad puntos posible de puntos.\\ \\
Con lo cual la suma del jugador 2 en r1...rl no puede ser mayor que la del jugador 2 en t2...tm, luego t2...tm es subsoluci\'on \'optima
\end{itemize}

Nuestra funci\'on recursiva se basa en eso, el jugador en cada turno para jugar de manera \'optima deber\'a tomar las cartas que maximizen (o minimize si es negativa) la diferencia de puntos sumados en su turno con respecto al turno siguiente del rival. \\
\\
Luego nos queda, para cada posible robo de cartas en el turno k:
$$MejorRobo(k) = puntosJugada(k) - MejorRobo(k+1)$$
Y nos quedaremos con el MejorRobo(k) mas alto de entre todos los puntosJugada(k) que tengamos (uno por cada robo de cartas diferente posible en el turno k) 



\newpage
\section{Testing}

\subsection{Un solo turno}

\begin{tabular}{| l | l |}
\hline
~~~Mazo \\ \hline
5 2 -3 15 6  \\ \hline
\end{tabular}
\quad \quad 
\begin{tabular}{| l | l |}
\hline
~~~~~~~MatrizDiferencia\\ \hline
$
\begin{vmatrix}
-- & 7  & 10 & 19 & 25 \\
-- & -- & 5 & 14 & 20 \\
-- & -- & -- & 18 & 24 \\
-- & -- & -- & -- & 21 \\
-- & -- & -- & -- & -- \\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\quad \quad
\begin{tabular}{| l | l |}
\hline
~~~~~~~~MatrizJugadas\\ \hline
$
\begin{vmatrix}
-- & -2 & 2  & -4 & -5 \\
-- & -- & 1  & -1 & -4 \\
-- & -- & -- & -1 & -2 \\
-- & -- & -- & -- & -2 \\
-- & -- & -- & -- & -- \\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\quad \quad 
\begin{tabular}{| l | l |}
\hline
~Salida \\ \hline
1 25 0  \\ \hline
Der 5  \\ \hline
\end{tabular}
\\
\\
Se corresponde al caso donde la mejor jugada que puede hacer el jugador en el primer turno es robar todas las cartas.
\subsection{Todas cartas negativas}
\begin{tabular}{| l | l |}
\hline
~~~~~Mazo \\ \hline
-5 -2 -3 -15 -6  \\ \hline
\end{tabular}
\quad \quad 
\begin{tabular}{| l | l |}
\hline
~~~~~~~MatrizDiferencia\\ \hline
$
\begin{vmatrix}
-- & 3  & 0  & 5  & 5  \\
-- & -- & 1  & 10 & 10 \\
-- & -- & -- & 12 & -12 \\
-- & -- & -- & -- & 9  \\
-- & -- & -- & -- & -- \\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\quad \quad
\begin{tabular}{| l | l |}
\hline
~~~~~~~~MatrizJugadas\\ \hline
$
\begin{vmatrix}
-- & -1 & -2 & 3  & 2  \\
-- & -- & 1  & 2  & 1  \\
-- & -- & -- & 1  & 1  \\
-- & -- & -- & -- & -1 \\
-- & -- & -- & -- & -- \\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\quad \quad 
\begin{tabular}{| l | l |}
\hline
~Salida \\ \hline
4 -13 -18  \\ \hline
Izq 2 \\ \hline
Izq 1 \\ \hline
Der 1 \\ \hline
Izq 1 \\ \hline
\end{tabular}
\\
\\
Se corresponde al caso donde todos los valores de las cartas son negativos, por lo tanto los puntajes totales son negativos tambi\'en.
\subsection{Jugador 1 pierde siempre (MatrizDiferencia[0][n-1]<0)}
\begin{tabular}{| l | l |}
\hline
~~~~~Mazo \\ \hline
2 3 -100 5 -6  \\ \hline
\end{tabular}
\quad \quad 
\begin{tabular}{| l | l |}
\hline
~~~~~~~MatrizDiferencia\\ \hline
$
\begin{vmatrix}
-- & 5  & 105 & 94  & -84  \\
-- & -- & 103 & -92 & 86 \\
-- & -- & --  & 105 & 99 \\
-- & -- & --  & --  & 11 \\
-- & -- & --  & --  & -- \\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\quad \quad
\begin{tabular}{| l | l |}
\hline
~~~~~~~~MatrizJugadas\\ \hline
$
\begin{vmatrix}
-- & -2 & 2  & 1  & 1  \\
-- & -- & 1  & -3 & -1 \\
-- & -- & -- & -1 & -2 \\
-- & -- & -- & -- & 1 \\
-- & -- & -- & -- & -- \\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\quad \quad 
\begin{tabular}{| l | l |}
\hline
~Salida \\ \hline
3 -90 -6  \\ \hline
Izq 1 \\ \hline
Der 1 \\ \hline
Der 3 \\ \hline
\end{tabular}
\\
\\
Se corresponde al caso donde el jugador 1 no tiene posibilidades de ganar elija lo que elija en el primer turno. 
\subsection{La suma total da 0}
\begin{tabular}{| l | l |}
\hline
~~~~Mazo \\ \hline
10 -50 -50 10 \\ \hline
\end{tabular}
\quad \quad 
\begin{tabular}{| l | l |}
\hline
~~~~MatrizDiferencia\\ \hline
$
\begin{vmatrix}
-- & 60 & 10 & 0  \\
-- & -- & 0  & 10 \\
-- & -- & -- & 60 \\
-- & -- & -- & -- \\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\quad \quad
\begin{tabular}{| l | l |}
\hline
~~~~~MatrizJugadas\\ \hline
$
\begin{vmatrix}
-- & 1  & 1  & -1  \\
-- & -- & -1 & -1  \\
-- & -- & -- & -1 \\
-- & -- & -- & --  \\

\end{vmatrix}
$
\\ \hline
\end{tabular}
\quad \quad 
\begin{tabular}{| l | l |}
\hline
~Salida \\ \hline
4 -40 -40  \\ \hline
Der 1 \\ \hline
Izq 1 \\ \hline
Der 1 \\ \hline
Izq 1 \\ \hline
\end{tabular}
\\
\\
Se corresponde al caso borde donde ambos jugador suman la misma cantidad de puntos

















\newpage
\section{Resultados}
Para graficar la performance de nuestro algoritmo se decidi\'o ir variando la cantidad de cartas y tomar los tiempos de ejecuci\'on.\\ \\
Si bien los tiempos var\'ian muy poco, se decidi\'o crear 20 instancias diferentes para cada cantidad de cartas distinta y tomar el promedio para suavizar un poco la curva.\\
Los valores de las cartas se tomaron al azar entre -99 y 99.

\\
\\
\includegraphics[width=16cm]{./Robanumeros/grafico2.png}
\\
\\
Para comparar con la cota de complejidad te\'orica se decidi\'o dividir los valores de tiempo calculados por $n^2$, siendo n la cantidad de cartas.\\
Con esto esperabamos obtener un gr\'afico de apariencia lineal ya que la complejidad te\'orica era $n^3$\\ \\
Los resultados fueron los siguientes:
\\
\\
\includegraphics[width=16cm]{./Robanumeros/grafico3.png}
\\
\\
Efectivamente como adelantamos, el gr\'afico se asemeja bastante al de una funci\'on lineal.
\newpage

Por \'ultimo, se decidi\'o comparar el tiempo de ejecuci\'on de casos triviales vs los aleatoreos calculados anteriormente.\\ \\
Para los casos triviales generaremos los valores de cartas entre 0 y 99, luego al primer jugador lo \'unico que deber\'a hacer es levantar todas las cartas en el primer turno.
\\
\\
\includegraphics[width=16cm]{./Robanumeros/grafico4.png}
\\
\\
Como podemos ver, los tiempos de ejecuci\'on son practicamente los mismos.\\
Esto se debe a que, aunque la soluci\'on sea trivial, nuestro algoritmo igualmente se ocupar\'a de llenar todas las posiciones de las matrices. 

\section{Adicionales}

La \'unica modificaci\'on que deber\'a hacerse ser\'a la siguiente:
\begin{itemize}
\item Si la mejor jugada que el jugador puede hacer en el turno tiene menor valor que la mejor jugada que puede hacer el otro jugador en el siguiente turno, tomaremos un comod\'in \\
\end{itemize}
Como esta diferencia de valores es exactamente lo que guardamos en nuestra \textbf{matrizDiferencia}, lo \'unico que deberemos cambiar es la manera de devolver el resultado:\\
\\
Cuando estemos analizando la posici\'on [i][j] de \textbf{matrizJugadas}, chequearemos el signo del valor en la misma posici\'on pero en \textbf{matrizDiferencia}.
\begin{itemize}
\item Si es positivo, seguimos operando como en el algoritmo original
\item Si es negativo y quedan comodines, anotaremos que en ese turno se toma uno y volveremos a analizar la misma posici\'on [i][j] (pero teniendo un comodin menos).
\end{itemize}
\\
\\
Si la cantidad de comodines es menor que la cantidad de cartas, la complejidad de no se ver\'a afetada. \\ 
En el caso de que sea mayor, la complejidad ser\'a $O(n^3 + k)$, siendo k la cantidad de comodines.





